<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="utf-8">
    <title>src/collision/GridBroadphase.js - cannon</title>
    <link rel="stylesheet" href="http://yui.yahooapis.com/3.9.1/build/cssgrids/cssgrids-min.css">
    <link rel="stylesheet" href="../assets/vendor/prettify/prettify-min.css">
    <link rel="stylesheet" href="../assets/css/main.css" id="site_styles">
    <link rel="icon" href="../assets/favicon.ico">
    <script src="http://yui.yahooapis.com/combo?3.9.1/build/yui/yui-min.js"></script>
</head>
<body class="yui3-skin-sam">

<div id="doc">
    <div id="hd" class="yui3-g header">
        <div class="yui3-u-3-4">
                <h1><img src="../assets/css/logo.png" title="cannon" width="117" height="52"></h1>
        </div>
        <div class="yui3-u-1-4 version">
            <em>API Docs for: 0.6.1</em>
        </div>
    </div>
    <div id="bd" class="yui3-g">

        <div class="yui3-u-1-4">
            <div id="docs-sidebar" class="sidebar apidocs">
                <div id="api-list">
                    <h2 class="off-left">APIs</h2>
                    <div id="api-tabview" class="tabview">
                        <ul class="tabs">
                            <li><a href="#api-classes">Classes</a></li>
                            <li><a href="#api-modules">Modules</a></li>
                        </ul>
                
                        <div id="api-tabview-filter">
                            <input type="search" id="api-filter" placeholder="Type to filter APIs">
                        </div>
                
                        <div id="api-tabview-panel">
                            <ul id="api-classes" class="apis classes">
                                <li><a href="../classes/AABB.html">AABB</a></li>
                                <li><a href="../classes/ArrayCollisionMatrix.html">ArrayCollisionMatrix</a></li>
                                <li><a href="../classes/Body.html">Body</a></li>
                                <li><a href="../classes/Box.html">Box</a></li>
                                <li><a href="../classes/Broadphase.html">Broadphase</a></li>
                                <li><a href="../classes/ConeEquation.html">ConeEquation</a></li>
                                <li><a href="../classes/ConeTwistConstraint.html">ConeTwistConstraint</a></li>
                                <li><a href="../classes/Constraint.html">Constraint</a></li>
                                <li><a href="../classes/ContactEquation.html">ContactEquation</a></li>
                                <li><a href="../classes/ContactMaterial.html">ContactMaterial</a></li>
                                <li><a href="../classes/ConvexPolyhedron.html">ConvexPolyhedron</a></li>
                                <li><a href="../classes/Cylinder.html">Cylinder</a></li>
                                <li><a href="../classes/Demo.html">Demo</a></li>
                                <li><a href="../classes/DistanceConstraint.html">DistanceConstraint</a></li>
                                <li><a href="../classes/Equation.html">Equation</a></li>
                                <li><a href="../classes/EventTarget.html">EventTarget</a></li>
                                <li><a href="../classes/FrictionEquation.html">FrictionEquation</a></li>
                                <li><a href="../classes/GridBroadphase.html">GridBroadphase</a></li>
                                <li><a href="../classes/GSSolver.html">GSSolver</a></li>
                                <li><a href="../classes/Heightfield.html">Heightfield</a></li>
                                <li><a href="../classes/HingeConstraint.html">HingeConstraint</a></li>
                                <li><a href="../classes/JacobianElement.html">JacobianElement</a></li>
                                <li><a href="../classes/LockConstraint.html">LockConstraint</a></li>
                                <li><a href="../classes/Mat3.html">Mat3</a></li>
                                <li><a href="../classes/Material.html">Material</a></li>
                                <li><a href="../classes/NaiveBroadphase.html">NaiveBroadphase</a></li>
                                <li><a href="../classes/Narrowphase.html">Narrowphase</a></li>
                                <li><a href="../classes/ObjectCollisionMatrix.html">ObjectCollisionMatrix</a></li>
                                <li><a href="../classes/Octree.html">Octree</a></li>
                                <li><a href="../classes/OctreeNode.html">OctreeNode</a></li>
                                <li><a href="../classes/Particle.html">Particle</a></li>
                                <li><a href="../classes/Plane.html">Plane</a></li>
                                <li><a href="../classes/PointToPointConstraint.html">PointToPointConstraint</a></li>
                                <li><a href="../classes/Pool.html">Pool</a></li>
                                <li><a href="../classes/Quaternion.html">Quaternion</a></li>
                                <li><a href="../classes/Ray.html">Ray</a></li>
                                <li><a href="../classes/RaycastResult.html">RaycastResult</a></li>
                                <li><a href="../classes/RaycastVehicle.html">RaycastVehicle</a></li>
                                <li><a href="../classes/RigidVehicle.html">RigidVehicle</a></li>
                                <li><a href="../classes/RotationalEquation.html">RotationalEquation</a></li>
                                <li><a href="../classes/RotationalMotorEquation.html">RotationalMotorEquation</a></li>
                                <li><a href="../classes/SAPBroadphase.html">SAPBroadphase</a></li>
                                <li><a href="../classes/Shape.html">Shape</a></li>
                                <li><a href="../classes/Solver.html">Solver</a></li>
                                <li><a href="../classes/Sphere.html">Sphere</a></li>
                                <li><a href="../classes/SPHSystem.html">SPHSystem</a></li>
                                <li><a href="../classes/SplitSolver.html">SplitSolver</a></li>
                                <li><a href="../classes/Spring.html">Spring</a></li>
                                <li><a href="../classes/Transform.html">Transform</a></li>
                                <li><a href="../classes/Trimesh.html">Trimesh</a></li>
                                <li><a href="../classes/TupleDictionary.html">TupleDictionary</a></li>
                                <li><a href="../classes/Vec3.html">Vec3</a></li>
                                <li><a href="../classes/Vec3Pool.html">Vec3Pool</a></li>
                                <li><a href="../classes/WheelInfo.html">WheelInfo</a></li>
                                <li><a href="../classes/World.html">World</a></li>
                            </ul>
                
                            <ul id="api-modules" class="apis modules">
                            </ul>
                        </div>
                    </div>
                </div>
            </div>
        </div>
        <div class="yui3-u-3-4">
                <div id="api-options">
                    Show:
                    <label for="api-show-inherited">
                        <input type="checkbox" id="api-show-inherited" checked>
                        Inherited
                    </label>
            
                    <label for="api-show-protected">
                        <input type="checkbox" id="api-show-protected">
                        Protected
                    </label>
            
                    <label for="api-show-private">
                        <input type="checkbox" id="api-show-private">
                        Private
                    </label>
                    <label for="api-show-deprecated">
                        <input type="checkbox" id="api-show-deprecated">
                        Deprecated
                    </label>
            
                </div>
            
            <div class="apidocs">
                <div id="docs-main">
                    <div class="content">
<h1 class="file-heading">File: src/collision/GridBroadphase.js</h1>

<div class="file">
    <pre class="code prettyprint linenums">
module.exports = GridBroadphase;

var Broadphase = require(&#x27;./Broadphase&#x27;);
var Vec3 = require(&#x27;../math/Vec3&#x27;);
var Shape = require(&#x27;../shapes/Shape&#x27;);

/**
 * Axis aligned uniform grid broadphase.
 * @class GridBroadphase
 * @constructor
 * @extends Broadphase
 * @todo Needs support for more than just planes and spheres.
 * @param {Vec3} aabbMin
 * @param {Vec3} aabbMax
 * @param {Number} nx Number of boxes along x
 * @param {Number} ny Number of boxes along y
 * @param {Number} nz Number of boxes along z
 */
function GridBroadphase(aabbMin,aabbMax,nx,ny,nz){
    Broadphase.apply(this);
    this.nx = nx || 10;
    this.ny = ny || 10;
    this.nz = nz || 10;
    this.aabbMin = aabbMin || new Vec3(100,100,100);
    this.aabbMax = aabbMax || new Vec3(-100,-100,-100);
	var nbins = this.nx * this.ny * this.nz;
	if (nbins &lt;= 0) {
		throw &quot;GridBroadphase: Each dimension&#x27;s n must be &gt;0&quot;;
	}
    this.bins = [];
	this.binLengths = []; //Rather than continually resizing arrays (thrashing the memory), just record length and allow them to grow
	this.bins.length = nbins;
	this.binLengths.length = nbins;
	for (var i=0;i&lt;nbins;i++) {
		this.bins[i]=[];
		this.binLengths[i]=0;
	}
}
GridBroadphase.prototype = new Broadphase();
GridBroadphase.prototype.constructor = GridBroadphase;

/**
 * Get all the collision pairs in the physics world
 * @method collisionPairs
 * @param {World} world
 * @param {Array} pairs1
 * @param {Array} pairs2
 */
var GridBroadphase_collisionPairs_d = new Vec3();
var GridBroadphase_collisionPairs_binPos = new Vec3();
GridBroadphase.prototype.collisionPairs = function(world,pairs1,pairs2){
    var N = world.numObjects(),
        bodies = world.bodies;

    var max = this.aabbMax,
        min = this.aabbMin,
        nx = this.nx,
        ny = this.ny,
        nz = this.nz;

	var xstep = ny*nz;
	var ystep = nz;
	var zstep = 1;

    var xmax = max.x,
        ymax = max.y,
        zmax = max.z,
        xmin = min.x,
        ymin = min.y,
        zmin = min.z;

    var xmult = nx / (xmax-xmin),
        ymult = ny / (ymax-ymin),
        zmult = nz / (zmax-zmin);

    var binsizeX = (xmax - xmin) / nx,
        binsizeY = (ymax - ymin) / ny,
        binsizeZ = (zmax - zmin) / nz;

	var binRadius = Math.sqrt(binsizeX*binsizeX + binsizeY*binsizeY + binsizeZ*binsizeZ) * 0.5;

    var types = Shape.types;
    var SPHERE =            types.SPHERE,
        PLANE =             types.PLANE,
        BOX =               types.BOX,
        COMPOUND =          types.COMPOUND,
        CONVEXPOLYHEDRON =  types.CONVEXPOLYHEDRON;

    var bins=this.bins,
		binLengths=this.binLengths,
        Nbins=this.bins.length;

    // Reset bins
    for(var i=0; i!==Nbins; i++){
        binLengths[i] = 0;
    }

    var ceil = Math.ceil;
	var min = Math.min;
	var max = Math.max;

	function addBoxToBins(x0,y0,z0,x1,y1,z1,bi) {
		var xoff0 = ((x0 - xmin) * xmult)|0,
			yoff0 = ((y0 - ymin) * ymult)|0,
			zoff0 = ((z0 - zmin) * zmult)|0,
			xoff1 = ceil((x1 - xmin) * xmult),
			yoff1 = ceil((y1 - ymin) * ymult),
			zoff1 = ceil((z1 - zmin) * zmult);

		if (xoff0 &lt; 0) { xoff0 = 0; } else if (xoff0 &gt;= nx) { xoff0 = nx - 1; }
		if (yoff0 &lt; 0) { yoff0 = 0; } else if (yoff0 &gt;= ny) { yoff0 = ny - 1; }
		if (zoff0 &lt; 0) { zoff0 = 0; } else if (zoff0 &gt;= nz) { zoff0 = nz - 1; }
		if (xoff1 &lt; 0) { xoff1 = 0; } else if (xoff1 &gt;= nx) { xoff1 = nx - 1; }
		if (yoff1 &lt; 0) { yoff1 = 0; } else if (yoff1 &gt;= ny) { yoff1 = ny - 1; }
		if (zoff1 &lt; 0) { zoff1 = 0; } else if (zoff1 &gt;= nz) { zoff1 = nz - 1; }

		xoff0 *= xstep;
		yoff0 *= ystep;
		zoff0 *= zstep;
		xoff1 *= xstep;
		yoff1 *= ystep;
		zoff1 *= zstep;

		for (var xoff = xoff0; xoff &lt;= xoff1; xoff += xstep) {
			for (var yoff = yoff0; yoff &lt;= yoff1; yoff += ystep) {
				for (var zoff = zoff0; zoff &lt;= zoff1; zoff += zstep) {
					var idx = xoff+yoff+zoff;
					bins[idx][binLengths[idx]++] = bi;
				}
			}
		}
	}

    // Put all bodies into the bins
    for(var i=0; i!==N; i++){
        var bi = bodies[i];
        var si = bi.shape;

        switch(si.type){
        case SPHERE:
            // Put in bin
            // check if overlap with other bins
            var x = bi.position.x,
                y = bi.position.y,
                z = bi.position.z;
            var r = si.radius;

			addBoxToBins(x-r, y-r, z-r, x+r, y+r, z+r, bi);
            break;

        case PLANE:
            if(si.worldNormalNeedsUpdate){
                si.computeWorldNormal(bi.quaternion);
            }
            var planeNormal = si.worldNormal;

			//Relative position from origin of plane object to the first bin
			//Incremented as we iterate through the bins
			var xreset = xmin + binsizeX*0.5 - bi.position.x,
				yreset = ymin + binsizeY*0.5 - bi.position.y,
				zreset = zmin + binsizeZ*0.5 - bi.position.z;

            var d = GridBroadphase_collisionPairs_d;
			d.set(xreset, yreset, zreset);

			for (var xi = 0, xoff = 0; xi !== nx; xi++, xoff += xstep, d.y = yreset, d.x += binsizeX) {
				for (var yi = 0, yoff = 0; yi !== ny; yi++, yoff += ystep, d.z = zreset, d.y += binsizeY) {
					for (var zi = 0, zoff = 0; zi !== nz; zi++, zoff += zstep, d.z += binsizeZ) {
						if (d.dot(planeNormal) &lt; binRadius) {
							var idx = xoff + yoff + zoff;
							bins[idx][binLengths[idx]++] = bi;
						}
					}
				}
			}
            break;

        default:
			if (bi.aabbNeedsUpdate) {
				bi.computeAABB();
			}

			addBoxToBins(
				bi.aabb.lowerBound.x,
				bi.aabb.lowerBound.y,
				bi.aabb.lowerBound.z,
				bi.aabb.upperBound.x,
				bi.aabb.upperBound.y,
				bi.aabb.upperBound.z,
				bi);
            break;
        }
    }

    // Check each bin
    for(var i=0; i!==Nbins; i++){
		var binLength = binLengths[i];
		//Skip bins with no potential collisions
		if (binLength &gt; 1) {
			var bin = bins[i];

			// Do N^2 broadphase inside
			for(var xi=0; xi!==binLength; xi++){
				var bi = bin[xi];
				for(var yi=0; yi!==xi; yi++){
					var bj = bin[yi];
					if(this.needBroadphaseCollision(bi,bj)){
						this.intersectionTest(bi,bj,pairs1,pairs2);
					}
				}
			}
		}
    }

//	for (var zi = 0, zoff=0; zi &lt; nz; zi++, zoff+= zstep) {
//		console.log(&quot;layer &quot;+zi);
//		for (var yi = 0, yoff=0; yi &lt; ny; yi++, yoff += ystep) {
//			var row = &#x27;&#x27;;
//			for (var xi = 0, xoff=0; xi &lt; nx; xi++, xoff += xstep) {
//				var idx = xoff + yoff + zoff;
//				row += &#x27; &#x27; + binLengths[idx];
//			}
//			console.log(row);
//		}
//	}

    this.makePairsUnique(pairs1,pairs2);
};

    </pre>
</div>
                    </div>
                </div>
            </div>
        </div>
    </div>
</div>
<script src="../assets/vendor/prettify/prettify-min.js"></script>
<script>prettyPrint();</script>
<script src="../assets/js/yui-prettify.js"></script>
<script src="../assets/../api.js"></script>
<script src="../assets/js/api-filter.js"></script>
<script src="../assets/js/api-list.js"></script>
<script src="../assets/js/api-search.js"></script>
<script src="../assets/js/apidocs.js"></script>
</body>
</html>
